(*
 * Materialien zu den zentralen Abiturpruefungen
 * im Fach Informatik ab 2012 in Nordrhein-Westfalen.
 *
 * Klassen TGraphNode, TGraph
 *
 * NW-Arbeitsgruppe:
 * Materialentwicklung zum Zentralabitur im Fach Informatik
 *
 * Version 2010-12-28
 *)
UNIT mGraph;

interface
uses mList;

type
  TGraphNode = class
  private
    marked: boolean;
    name: string;
    edges: TList;
  public
    constructor create(pName: string); virtual;
    procedure mark; virtual;
    procedure unmark; virtual;
    function isMarked: boolean; virtual;
    function getName: string; virtual;
    destructor destroy; override;
  private
    procedure addEdge(pNode: TGraphNode; pWeight: double); virtual;
    function getEdgeWeight(pNode: TGraphNode): double; virtual;
    procedure removeEdge(pNode: TGraphNode); virtual;
    function getNeighbours: TList; virtual;
  end;

  TEdge = class
  private
    neighbour: TGraphNode;
    weight: double;
    constructor create(pNeighbour: TGraphNode; pWeight: double); virtual;
    function getNeighbour: TGraphNode; virtual;
    function getWeight: double; virtual;
    destructor destroy; override;
   end;

   TGraph = class
   private
     nodeList: TList;
   public
     constructor create; virtual;
     function isEmpty: boolean; virtual;
     procedure addNode(pNode: TGraphNode); virtual;
     function hasNode(pName: string): boolean; virtual;
     function getNode(pName: string): TGraphNode; virtual;
     procedure removeNode(pNode: TGraphNode); virtual;
     procedure addEdge(pNode1, pNode2: TGraphNode; pWeight: double); virtual;
     function hasEdge(pNode1, pNode2: TGraphNode): boolean; virtual;
     procedure removeEdge(pNode1, pNode2: TGraphNode); virtual;
     function getEdgeWeight(pNode1, pNode2: TGraphNode): double; virtual;
     procedure resetMarks; virtual;
     function allNodesMarked: boolean; virtual;
     function getNodes: TList; virtual;
     function getNeighbours(pNode: TGraphNode): TList; virtual;
     destructor destroy; override;
   end;

implementation

// TGraphNode

constructor TGraphNode.create(pName: string);
begin
  marked := false;
  name := pName;
  edges := TList.create;
end;

procedure TGraphNode.mark;
begin
  marked := true;
end;

procedure TGraphNode.unmark;
begin
  marked := false;
end;

function TGraphNode.isMarked: boolean;
begin
  result := marked;
end;

function TGraphNode.getName: string;
begin
  result := name;
end;

destructor TGraphNode.destroy;
begin
  while not edges.isEmpty do
  begin
    edges.toLast;
    edges.remove;
  end;
end;

// TGraphNode - Hilfsmethoden

procedure TGraphNode.addEdge(pNode: TGraphNode; pWeight: double);
begin
  if pNode <> nil then
  begin
    edges.append(TEdge.create(pNode,pWeight));
  end;
end;

function TGraphNode.getEdgeWeight(pNode: TGraphNode): double;
var
  edgeAkt: TEdge;
  finished: boolean;
begin
  result := -1;
  if pNode <> nil then
  begin
    edges.toFirst;
    finished := false;
    while edges.hasAccess and not finished do
    begin
     edgeAkt := TEdge(edges.getObject);
     if edgeAkt.getNeighbour = pNode then
     begin
       result := edgeAkt.getWeight;
       finished := true;
     end;
     edges.next;
    end;
  end;
end;

procedure TGraphNode.removeEdge(pNode: TGraphNode);
var
  removed: boolean;
begin
  if pNode <> nil then
  begin
    removed := false;
    edges.toFirst;
    while edges.hasAccess and not removed do
    begin
      if pNode = TEdge(edges.getObject).getNeighbour then
      begin
        edges.remove;
        removed := true;
      end;
      edges.next;
    end;
  end;
end;

function TGraphNode.getNeighbours: TList;
var
  neighbourList: TList;
begin
  neighbourList := TList.create;
  if not edges.isEmpty then
  begin
    edges.toFirst;
    while edges.hasAccess do
    begin
      neighbourList.append(TEdge(edges.getObject).getNeighbour);
      edges.next;
    end;
  end;
 result := neighbourList;
end;

// Ende - TGraphNode

// TEdge

constructor TEdge.create(pNeighbour: TGraphNode; pWeight: double);
begin
  neighbour := pNeighbour;
  weight := pWeight;
end;

function TEdge.getNeighbour: TGraphNode;
begin
  result := neighbour;
end;

function TEdge.getWeight : double;
begin
  result := weight;
end;

destructor TEdge.destroy;
begin
  inherited destroy;
end;

// TGraph

constructor TGraph.create;
begin
  nodeList := TList.create;
end;

function TGraph.isEmpty: boolean;
begin
  result := nodeList.isEmpty;
end;

procedure TGraph.addNode(pNode: TGraphNode);
begin
  if (pNode <> nil) and (not self.hasNode(pNode.getName)) then
    nodeList.append(pNode);
end;

function TGraph.hasNode(pName: string): boolean;
begin
  if not nodeList.isEmpty then
  begin
    nodeList.toFirst;
    while nodeList.hasAccess and
        (pName <> TGraphNode(nodeList.getObject).name)  do
      nodeList.next;
    if nodeList.hasAccess  then
      result := true
    else
      result := false;
  end
  else
    result := false;
end;

function TGraph.getNode(pName: string): TGraphNode;
begin
  nodeList.toFirst;
  while nodeList.hasAccess and
        (pName <> TGraphNode(nodeList.getObject).name)  do
    nodeList.next;
  if nodeList.hasAccess  then
    result := TGraphNode(nodeList.getObject)
  else
    result := nil;
end;

procedure TGraph.removeNode(pNode: TGraphNode);
var
  nodeAkt, nodeNeighbour: TGraphNode;
  neighbours: TList;
begin
  if pNode <> nil then
  begin
    nodeList.toFirst;
    while nodeList.hasAccess do
    begin
      nodeAkt := TGraphNode(nodeList.getObject);
      if nodeAkt.getName = pNode.getName then
      begin
        neighbours := self.getNeighbours(nodeAkt);
        if not neighbours.isEmpty then
        begin
          neighbours.toFirst;
          while neighbours.hasAccess do
          begin
            nodeNeighbour := TGraphNode(neighbours.getObject);
            self.removeEdge(nodeAkt,nodeNeighbour);
            neighbours.next;
          end;
        end;
        nodeList.remove;
      end;
      nodeList.next;
    end;
  end;
end;

procedure TGraph.addEdge(pNode1, pNode2: TGraphNode; pWeight: double);
begin
  if (pNode1 <> nil) and (pNode2 <> nil) then
  begin
    if self.hasEdge(pNode1,pNode2) then
      self.removeEdge(pNode1,pNode2);
    pNode1.addEdge(pNode2,pWeight);
    pNode2.addEdge(pNode1,pWeight);
  end;
end;

function TGraph.hasEdge(pNode1, pNode2: TGraphNode): boolean;
var
  nodeNeighbour: TGraphNode;
  neighbours: TList;
begin
  result := false;
  if (pNode1 <> nil) and (pNode2 <> nil) then
  begin
    neighbours := pNode1.getNeighbours;
    if not neighbours.isEmpty then
    begin
      neighbours.toFirst;
      while neighbours.hasAccess do
      begin
        nodeNeighbour := TGraphNode(neighbours.getObject);
        if nodeNeighbour.getName = pNode2.getName then
          result := true;
        neighbours.next;
      end;
    end;
  end;
end;

procedure TGraph.removeEdge(pNode1, pNode2: TGraphNode);
begin
  if (pNode1 <> nil) and (pNode2 <> nil)
    and self.hasEdge(pNode1,pNode2) then
  begin
    pNode1.removeEdge(pNode2);
    pNode2.removeEdge(pNode1);
  end;
end;

function TGraph.getEdgeWeight(pNode1, pNode2: TGraphNode): double;
begin
  result := pNode1.getEdgeWeight(pNode2);
end;

procedure TGraph.resetMarks;
begin
  if not nodeList.isEmpty then
  begin
    nodeList.toFirst;
    while nodeList.hasAccess do
    begin
      TGraphNode(nodeList.getObject).unmark;
      nodeList.next;
    end;
  end;
end;

function TGraph.allNodesMarked: boolean;
var
  allMarked: boolean;
begin
  allMarked := true;
  if not nodeList.isEmpty then
  begin
    nodeList.toFirst;
    while nodeList.hasAccess and allMarked do
    begin
      if not TGraphNode(nodeList.getObject).isMarked then
        allMarked := false;
      nodeList.next;
    end;
  end;
  result := allMarked;
end;

function TGraph.getNodes: TList;
var
  nodeListCopy: TList;
begin
  nodeListCopy:= TList.create;
  nodeList.toFirst;
  while nodeList.hasAccess do
  begin
    nodeListCopy.append(TGraphNode(nodeList.getObject));
    nodeList.next;
  end;
  result := nodeListCopy;
end;

function TGraph.getNeighbours(pNode: TGraphNode): TList;
begin
  if pNode <> nil then
    result := pNode.getNeighbours
  else
    result := TList.create;
end;

destructor TGraph.destroy;
begin
  nodeList.destroy;
  inherited destroy;
end;

end.
